package ljl.alg.wangzheng_camp.round1.twopointers;

/**
 * 有个内含单词的超大文本文件，
 * 给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。
 * 如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
 *
 * 示例：
 *
 * 输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
 * 输出：1
 *
 * 试了一下不区分顺序
 * */
public class _17_11_word_distance {
    
    /*
    * 先暴力吧 没想到好的办法
    *
    * 长度是 100000，一乘是 100 亿，这个肯定过不了
    *
    * 操！怎么过了！
    * */
    public int findClosest(String[] words, String word1, String word2) {
        int min = Integer.MAX_VALUE;
        boolean found = false;
        String secondWord = null;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                found = true;
                secondWord = word2;
            } else if (words[i].equals(word2)) {
                found = true;
                secondWord = word1;
            }
            if (!found) continue;
            for (int j = i + 1; j < words.length; j++) {
                if (words[j].equals(secondWord)) {
                    min = Math.min(min, j - i);
                    break;
                }
            }
            found = false;
        }
        return min;
    }
    
    /*
    * 我去 感觉被耍了
    * 不好想 你别看它简单
    *
    * 我小小优化一下快了 1ms，也算有点用
    *
    * */
    public int findClosest2(String[] words, String word1, String word2) {
        int length = words.length;
        int ans = length;
        int index1 = -1, index2 = -1;
        for (int i = 0; i < length; i++) {
            String word = words[i];
            boolean changed = false;
            if (word.equals(word1)) {
                changed = true;
                index1 = i;
            } else if (word.equals(word2)) {
                changed = true;
                index2 = i;
            }
            if (changed && index1 >= 0 && index2 >= 0) {
                ans = Math.min(ans, Math.abs(index1 - index2));
            }
        }
        return ans;
    }
    
}
